import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/26 9:56
 * @description 暴力枚举，O(n^2) 由于 n = 10^3，能够通过
 */
public class Solution {
    public static void main(String[] args) {

    }
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        List<Integer> heights = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 右端点为实际右端点减一，更好的覆盖重复区间
            int left1 = positions[i][0], right1 = left1 + positions[i][1] - 1;
            int height = positions[i][1];
            for (int j = 0; j < i; j++) {
                int left2 = positions[j][0], right2 = left2 + positions[j][1] - 1;
                if (right1 >= left2 && right2 >= left1) {
                    // 区间相交
                    height = Math.max(height, heights.get(j) + positions[i][1]);
                }
            }
            heights.add(height);
        }
        for (int i = 1; i < n; i++) {
            heights.set(i, Math.max(heights.get(i), heights.get(i-1)));
        }
        return heights;
    }
}
